var map = [
	[1,1,1,1,1,1,1,1,1,1],
	[1,1,1,1,1,1,1,1,1,1],
	[1,0,0,0,0,0,1,1,1,1],
	[1,1,1,1,1,0,1,0,0,1],
	[1,1,3,1,1,0,1,0,4,1],
	[1,1,1,1,1,0,1,0,0,1],
	[0,0,0,0,0,0,1,1,1,1],
	[1,1,1,1,1,1,1,1,1,1],
	[1,1,1,1,1,1,1,1,1,1],
	[1,1,1,1,1,1,1,1,1,1]
];

function 	Node(){
	this.row = '',
	this.rank = '',
	this.f = '',
	this.g = '',
	this.h = '',
	this.parent = null;//当前路径节点的前一个节点
}
/*计算两点之间的距离*/
function distance(x1, x2, y1, y2){
	return Math.sqrt((x1-y1)*(x1-y1)+(x2-y2)*(x2-y2));
}
/*判断时候找到终点*/
function isNodeInList(nodeEnd, listStart){
	for(var i in listStart){
		if(nodeEnd.row == listStart[i].row && nodeEnd.rank == listStart[i].rank){
			return true;
		}
	}
}
/*找到权值最小的节点*/
function getNearestNode(listStart){
	var node = new Node();
	var tempF = 1000000;
	var flag = true;
	for(var i = 0; i < listStart.length; i++){
		if(listStart[i].f < tempF){
			node = listStart[i];
			tempF = listStart[i].f;
			flag = false;
		}
	}
	if(flag)
		node = null;
	return node;
}
/*找到当前节点旁边的8个节点，父节点不能放，阻挡点不能放*/
function getNearestList(nowNode, listTemp, listStart, listEnd, nodeEnd){
	//一个节点周围的8个节点
	//把当前的走位的节点放到listTemp里
	//父节点、关闭列表里的、障碍物都不放
	
	for(var i = -1; i <= 1; i++){
		for(var j = -1; j <= 1; j++){
			if(i == 0 && j == 0){//是自己跳过
				continue;
			}
			var rowTemp = nowNode.row + i;
			var rankTemp = nowNode.rank + j;
			if(rowTemp < 0 || rankTemp < 0 || rowTemp > 9 || rankTemp > 9){//超过表格跳过
				continue;
			}
			if(map[rowTemp][rankTemp] == 0){//障碍物
				continue;
			}
			if(nowNode.parent != null){//父节点跳过
				if(nowNode.parent.row == rowTemp && nowNode.parent.rank == rankTemp){
					continue;
				}
			}
			//在开启列表的跳过
			var inStartList = false;
			for(var l in listStart){
				if(listStart[l].row == rowTemp && listStart[l].rank == rankTemp){
					inStartList = true;
					listTemp.push(listStart[l]);
					break;
				}
			}
			if(inStartList){
				continue;
			}
			//在关闭列表的跳过
			var inEndList = false;
			for(var k in listEnd){
				if(listEnd[k].row == rowTemp && listEnd[k].rank == rankTemp){
					inEndList = true;
					break;
				}
			}
			if(inEndList){
				continue;
			}
			var nearNode = new Node();
			nearNode.g = nowNode.g + distance(nowNode.row, nowNode.rank, rowTemp, rankTemp);
			nearNode.h = distance(rowTemp, rankTemp, nodeEnd.row, nodeEnd.rank);
			nearNode.f = nearNode.g + nearNode.h;
			nearNode.row = rowTemp;
			nearNode.rank = rankTemp;
			nearNode.parent = nowNode;
			listTemp.push(nearNode);
		}
	}
}
/*把当前节点从启动列表中删除*/
function EraseFromList(nowNode, listStart){
	for(var i in listStart){
		if(listStart[i].row == nowNode.row && listStart[i].rank == nowNode.rank){
			listStart.splice(i,1);
			break;
		}
	}
}
var str =[0,1,2,3,4,5,6,7,8,9];
/*计算路径*/
function calculate_path(){

	var rowStart, rowEnd, rankStart, rankEnd,
			nodeStart, nodeEnd, nowNode, newNode;
	var listStart = [];	//启动列表
	var listEnd = [];		//关闭列表
	var listTemp = [];	//临时节点，放旁边的节点
	for(var i = 0; i < 10; i++){
		for(var j = 0; j < 10; j++){
			if(map[i][j] == 3){
				rowStart = i;
				rankStart = j;
			}else if(map[i][j] == 4){
				rowEnd = i;
				rankEnd = j;
			}
		}
	}
	/*初始化起点*/
	nodeStart = new Node();
	nodeStart.row = rowStart;
	nodeStart.rank = rankStart;
	nodeStart.g = 0;
	nodeStart.h = distance(rowStart, rankStart, rowEnd, rankEnd);
	nodeStart.f = nodeStart.g + nodeStart.h;
	nodeStart.parent = null;
	/*初始化终点*/
	nodeEnd = new Node();
	nodeEnd.row = rowEnd;
	nodeEnd.rank = rankEnd;

	nowNode = null;		//当前节点

	listStart.push(nodeStart);	//把开始节点（起点）加入到启动列表
	/*循环判断终点是否在开启列表中，如果在说明已经找到路径*/
	while(!isNodeInList(nodeEnd, listStart)){
		if(nowNode === null){
			nowNode = getNearestNode(listStart);	//找权值最小的节点
			if(nowNode === null){
				alert('没有找到路径');
				break;
			}
		}
		//找到当前节点旁边的8个节点，父节点不能放，阻挡点不能放
		listTemp = [];
		getNearestList(nowNode, listTemp, listStart, listEnd, nodeEnd);
		//把当前节点放到关闭列表里面
		listEnd.push(nowNode);
		//把当前节点从开启列表中删除
		EraseFromList(nowNode, listStart);
		//把新找到的周围点放到开启列表中
		for(var a in listTemp){
			if(isNodeInList(listTemp[a], listStart))
				continue;
			listStart.push(listTemp[a]);
		}
		//重新再开启列表里找最小权值的节点
		newNode = getNearestNode(listStart);
		nowNode = newNode;
	}
	if(nowNode === null){
		alert('no');
		return;
	}
	var nodeFind = null;
	for(var i in listStart){
		if(listStart[i].row == nodeEnd.row && listStart[i].rank == nodeEnd.rank){
			nodeFind = listStart[i];
			break;
		}
	}
	if(nodeFind == null){
		alert('没有路径');
		return;
	}

	while(nodeFind){
		map[nodeFind.row][nodeFind.rank] = 2;
		nodeFind = nodeFind.parent;
	}

	for(var i = 0; i < 10; i++){
		for(var j = 0; j < 10; j++){
			if(map[i][j] == 0){
				str[i] += ' ■ ';
			}else if(map[i][j] == 1){
				str[i] += ' ○ ';
			}else if(map[i][j] == 2){
				str[i] += ' ☛ ';
			}else if(map[i][j] == 3){
				str[i] += ' ☺ ';
			}else if(map[i][j] == 4){
				str[i] += ' ☽ ';
			}

		}
		console.log(str[i]);
	}
}

calculate_path();